#include <stdio.h>

/*
 * 分块查找
 */

/*
  step1 先选取各块中的最大关键字构成一个索引表；[1] 
  step2 查找分两个部分：先对索引表进行二分查找或
  顺序查找，以确定待查记录在哪一块中；
  然后，在已确定的块中用顺序法进行查找。
*/

typedef int keytype;

typedef struct 
{
  keytype Key;
}elemtype;

typedef struct
{
  keytype Key;
  int Link;
}indextype;

/**
 * 分块查找关键字为Key的记录。索引表为ls[0]-ls[m-1],顺序表为s，块长为l
 */
int IndexSequelSearch(indextype ls[],elemtype s[],int m,int l,keytype Key)
{
  int i,j;
  /*在索引表中顺序查找*/
  i=0;
  while(i<m&&Key>ls[i].Key)i++;
	
  if(i>=m)
    return -1;
  else{
    /*在顺序表中顺序查找*/
    j=ls[i].Link;
    while(Key!=s[j].Key&&j-ls[i].Link<l)
      j++;
	
    if(Key==s[j].Key)
      return j;
    else 
      return -1; 
  }
}



struct index /*定义块的结构*/
{
  int key;
  int start;
  int end;
} index_table[4]; /*定义结构体数组*/

int block_search(int key, int a[]) /*自定义实现分块查找*/
{
  int i, j;
  i = 1;
  while (i <= 3 && key > index_table[i].key) /*确定在那个块中*/
    i++;
  if (i > 3) /*大于分得的块数，则返回0*/
    return 0;
  j = index_table[i].start; /*j等于块范围的起始值*/
  while (j <= index_table[i].end && a[j] != key) /*在确定的块内进行查找*/
    j++;
  if (j > index_table[i].end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/
    j = 0;
  return j;
}

main()
{
  int i, j = 0, k, key, a[16];
  printf("please input the number:\n");
  for (i = 1; i < 16; i++)
    scanf("%d", &a[i]); /*输入由小到大的15个数*/
  for (i = 1; i <= 3; i++)
    {
      index_table[i].start = j + 1; /*确定每个块范围的起始值*/
      j = j + 1;
      index_table[i].end = j + 4; /*确定每个块范围的结束值*/
      j = j + 4;
      index_table[i].key = a[j]; /*确定每个块范围中元素的最大值*/
    }
  printf("please input the number which do you want to search:\n");
  scanf("%d", &key); /*输入要查询的数值*/
  k = block_search(key, a); /*调用函数进行查找*/
  if (k != 0)
    printf("success.the position is :%d\n", k); /*如果找到该数，则输出其位置*/
  else
    printf("no found!"); /*若未找到则输出提示信息*/
}


